<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4825：[Hnoi2017]单旋</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Hnoi2017]单旋</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Hnoi2017]单旋</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Hnoi2017]单旋                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>H 国是一个热爱写代码的国家，那里的人们很小去学校学习写各种各样的数据结构。伸展树（splay）是一种数据</div>
<div>结构，因为代码好写，功能多，效率高，掌握这种数据结构成为了 H 国的必修技能。有一天，邪恶的&ldquo;卡&rdquo;带着</div>
<div>他的邪恶的&ldquo;常数&rdquo;来企图毁灭 H 国。&ldquo;卡&rdquo;给 H 国的人洗脑说，splay 如果写成单旋的，将会更快。&ldquo;卡&rdquo;称</div>
<div>&ldquo;单旋 splay&rdquo;为&ldquo;spaly&rdquo;。虽说他说的很没道理，但还是有 H 国的人相信了，小 H 就是其中之一，spaly 马</div>
<div>上成为他的信仰。 而 H 国的国王，自然不允许这样的风气蔓延，国王构造了一组数据，数据由 m 个操作构成，</div>
<div>他知道这样的数据肯定打垮 spaly，但是国王还有很多很多其他的事情要做，所以统计每个操作所需要的实际代价</div>
<div>的任务就交给你啦。</div>
<div></div>
<div>数据中的操作分为五种：</div>
<div></div>
<div>1. 插入操作：向当前非空 spaly 中插入一个关键码为 key 的新孤立节点。插入方法为，先让 key 和根比较，如果&nbsp;</div>
<div>key 比根小，则往左子树走，否则往右子树走，如此反复，直到某个时刻，key 比当前子树根 x 小，而 x 的左子</div>
<div>树为空，那就让 key 成为 x 的左孩子； 或者 key 比当前子树根 x 大，而 x 的右子树为空，那就让 key 成为&nbsp;</div>
<div>x 的右孩子。该操作的代价为：插入后，key 的深度。特别地，若树为空，则直接让新节点成为一个单个节点的树</div>
<div>。（各节点关键码互不相等。对于&ldquo;深度&rdquo;的解释见末尾对 spaly 的描述）。</div>
<div>2. 单旋最小值：将 spaly 中关键码最小的元素 xmin 单旋到根。操作代价为：单旋前 xmin 的深度。</div>
<div>（对于单旋操作的解释见末尾对 spaly 的描述）。</div>
<div>3. 单旋最大值：将 spaly 中关键码最大的元素 xmax 单旋到根。操作代价为：单旋前 xmax 的深度。</div>
<div>4. 单旋删除最小值：先执行 2 号操作,然后把根删除。由于 2 号操作之后,根没有左子树,所以直接切断根和右子</div>
<div>树的联系即可（具体见样例解释）。 操作代价同 2 号操 作。</div>
<div>5. 单旋删除最大值：先执行 3 号操作,然后把根删除。 操作代价同 3 号操作。</div>
<div><img src="../file/4825_0.jpg" width="452" height="220" alt="" /></div>
<div></div>
<div>对于不是 H 国的人，你可能需要了解一些 spaly 的知识，才能完成国王的任务：</div>
<div></div>
<div>a. spaly 是一棵二叉树，满足对于任意一个节点 x，它如果有左孩子 lx，那么 lx 的关键码小于 x 的关键码。</div>
<div>如果有右孩子 rx，那么 rx 的关键码大于 x 的关键码。</div>
<div>b. 一个节点在 spaly 的深度定义为：从根节点到该节点的路径上一共有多少个节点（包括自己）。</div>
<div>c. 单旋操作是对于一棵树上的节点 x 来说的。一开始,设 f 为 x 在树上的父亲。如果 x 为 f 的左孩子，那么</div>
<div>执行 zig(x) 操作（如上图中，左边的树经过 zig(x) 变为了右边的树），否则执行 zag(x) 操作（在上图中，将</div>
<div>右边的树经过 zag(f) 就变成了左边的树）。每当执 行一次 zig(x) 或者 zag(x)，x 的深度减小 1，如此反复，</div>
<div>直到 x 为根。总之，单旋 x 就是通过反复执行 zig 和 zag 将 x 变为根。</div></p><hr/><h3>输入格式</h3><p><div>第一行单独一个正整数 m。</div>
<div>接下来 m 行，每行描述一个操作：首先是一个操作编号 c&isin;[1,5]，即问题描述中给出的五种操作中的编号，若 c</div>
<div>&nbsp;= 1，则再输入一个非负整数 key，表示新插入节点的关键码。</div>
<div>1&le;m&le;10^5,1&le;key&le;10^9</div>
<div>所有出现的关键码互不相同。任何一个非插入操作，一定保证树非空。在未执行任何操作之前，树为空</div></p><hr/><h3>输出格式</h3><p><div>输出共 m 行，每行一个整数，第 i 行对应第 i 个输入的操作的代价。</div></p><hr/><h3>样例输入</h3><pre>5
1 2
1 1
1 3
4
5</pre><hr/><h3>样例输出</h3><pre>1
2
2
2
2
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4825" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4825" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>